#include <iostream>
#include <vector>
#include <string>
#include <cstring>
#include <algorithm>
using namespace std;

namespace OpenHash
{
	template<class T>
	class HashFunc
	{
	public:
		size_t operator()(const T& val)
		{
			return val;
		}
	};

	template<> //特化
	class HashFunc<string>
	{
	public:
		size_t operator()(const string& s) 
		{
			const char* str = s.c_str();
			unsigned int seed = 131; // 31 131 1313 13131 131313
			unsigned int hash = 0;
			while (*str)
			{
				hash = hash * seed + (*str++);
			}

			return hash;
		}
	};

	template<class V>
	struct HashBucketNode
	{
		HashBucketNode<V>* _pNext;
		V _data;

		HashBucketNode(const V& data)
			: _pNext(nullptr), _data(data)
		{}
		
	};

	// 本文所实现的哈希桶中key是唯一的
	template<class V, class HF = HashFunc<V>>
	class HashBucket
	{
		typedef HashBucketNode<V> Node;
		typedef Node* PNode;

		typedef HashBucket<V, HF> Self;

	public:
		/*HashBucket(size_t capacity)
			: _table(GetNextPrime(capacity))
			, _size(0)
		{}*/

		HashBucket()
		{
			_table.resize(10, nullptr);
		}

		~HashBucket()
		{
			Clear();
		}

		// 哈希桶中的元素不能重复
		Node* Insert(const V& data)
		{ 
			// 1. 检测是否需要扩容
			CheckCapacity();

			//2. 通过设计的哈希函数确定data所在桶号
			size_t pos = HashFunc(data) % _table.size();

			/* 3. 检测该元素是否在bucketNo桶中
			    本质：检测链表中是否存在data的节点*/
			Node* pCur = _table[pos];
			while (pCur)
			{
				if (pCur->_data == data) return nullptr;
				pCur = pCur->_pNext;
			}

			// 4. 插入新节点，头插
			pCur = new Node(data);
			pCur->_pNext = _table[pos]; 
			_table[pos] = pCur;
			++_size;

			return pCur;
		}

		// 删除哈希桶中为data的元素(data不会重复)
		bool Erase(const V& data)
		{
			size_t pos = HashFunc(data) % _table.size();
			Node* pCur = _table[pos];
			Node* pPre = nullptr; //保存其头节点
			while (pCur) {
				if (pCur->_data == data) { 
					//当第一个节点就是我们要删除节点
					//if (_table[pos] == pCur) _table[pos] = pCur->_pNext; //法一
					if (prev == nullptr) _table[pos] = pCur->_pNext; //法二
					else pPre->_pNext = pCur->_pNext; //删除的节点不是第一个节点

					delete pCur;
					--_size;
					return true;
				}
				pPre = pCur;
				pCur = pCur->_pNext;
			}
			return false;
		}

		Node* Find(const V& data)
		{
			size_t pos = HashFunc(data) % _table.size();//string在桶的映射
			Node* pCur = _table[pos];
			while (pCur) {
				if (pCur->_data == data) return pCur;
				pCur = pCur->_pNext;
			}
			return nullptr;
		}

		size_t Size()const
		{
			return _size;
		}

		bool Empty()const
		{
			return 0 == _size;
		}

		void Clear() //销毁哈希桶
		{
			for (size_t i = 0; i < _table.size(); i++)
			{
				Node* pCur = _table[i];
				while (pCur)
				{
					Node* next = pCur->_pNext;
					delete pCur;
					pCur = next;
				}
				_table[i] = nullptr;
			}
			_size = 0; //有效元素清零
		}

		size_t BucketCount()const
		{
			return _table.capacity();
		}

		void Swap(Self& ht)
		{
			_table.swap(ht._table);
			swap(_size, ht._size);
		}

	private:
		size_t HashFunc(const V& data)
		{
			return HF()(data) % _table.capacity();
		}

		void CheckCapacity()
		{
			if (_size == _table.size())
			{				
				vector<Node*> newtable(_table.size() * 2, nullptr);

				for (size_t i = 0; i < _table.size(); i++)
				{
					Node* pCur = _table[i];
					while (pCur)
					{
						// 将pCur节点从旧哈希桶搬移到新哈希桶
						// 1. 将pCur节点从旧链表中删除
						Node* next = pCur->_pNext;
						//_table[i] = pCur->_pNext;
				
						// 2. 将pCur节点插入到新链表中
						size_t pos = HashFunc(pCur->_data) % newtable.size();

						// 3. 插入节点--->头插
						pCur->_pNext = newtable[pos];
						newtable[pos] = pCur;

						pCur = next;
					}
					_table[i] = nullptr;
				}
				_table.swap(newtable);
				_size = newtable.size();
				
			}
		}

	private:
		vector<Node*> _table;
		size_t _size = 0;    // 哈希表中有效元素的个数
	};

}


void TestHT()
{
	OpenHash::HashBucket<string> ht;


	ht.Insert( "sort" );
	ht.Insert("left");
	ht.Insert( "rightt");
	ht.Insert( "left");
	
}

int main()
{
	TestHT();
}